/**
 * 面积的算法是取第i个柱子，找到左右两侧第一个小于或等于的柱子m和n，m+1和n-1即为矩形的两边
 * 所以单调栈的存储，从栈顶到栈底递减。这样栈顶和栈顶的下一个元素，和即将小于栈顶的元素，即为符合条件的
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
    let leftClosestMin = new Array(heights.length).fill(0),
        rightClosestMin = new Array(heights.length).fill(0),
        area = 0;

    let stack = []
    for (let i = 0; i < heights.length; i++) {
        while (stack.length > 0 && heights[i] <= heights[stack[stack.length - 1]]) {
            stack.pop()
        }
        // index为0时，左侧最小值为-1，i处的值入栈时，目前栈顶的值为左侧最接近的比他小的值
        leftClosestMin[i] = stack.length > 0 ? stack[stack.length - 1] : -1
        stack.push(i)
    }

    stack = []
    for (let i = heights.length - 1; i >= 0; i--) {
        while (stack.length > 0 && heights[i] <= heights[stack[stack.length - 1]]) {
            stack.pop()
        }
        // index为最右侧时，右边为length，i处的值入栈时，目前栈顶的值为右侧最接近的比他小的值
        rightClosestMin[i] = stack.length > 0 ? stack[stack.length - 1] : heights.length
        stack.push(i)
    }

    for (let i = 0; i < heights.length; i++) {
        area = Math.max(area,heights[i] * (rightClosestMin[i] - leftClosestMin[i] - 1))
    }

    return area
};


/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
    let leftClosestMin = new Array(heights.length).fill(0),
        rightClosestMin = new Array(heights.length).fill(heights.length),
        area = 0;

    let stack = []
    for (let i = 0; i < heights.length; i++) {
        while (stack.length > 0 && heights[i] <= heights[stack[stack.length - 1]]) {
            // 出栈时，当前i处的值就是最接近i处比i小的值
            let index = stack.pop()
            rightClosestMin[index] = i
        }
        leftClosestMin[i] = stack.length > 0 ? stack[stack.length - 1] : -1
        stack.push(i)
    }

    for (let i = 0; i < heights.length; i++) {
        area = Math.max(area, heights[i] * (rightClosestMin[i] - leftClosestMin[i] - 1))
    }

    return area
};